package a_doubleWrite;

import util.ListNode;

/**
 * todo
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-28 10:04
 */
public class L147 {
    //    public ListNode insertionSortList(ListNode head) {
//        if(head==null||head.next==null) return head;
//        ListNode dummy=new ListNode(0);
//        ListNode node=head;
//        while(node!=null){
//            // 先记录当前的下一个节点,后面node会修改
//            ListNode next = node.next;
//            ListNode cur=dummy.next,pre=dummy;
//            while(cur!=null){
//                // 直到找到要插入节点比当前节点小的
//                if(node.val>cur.val){
//                    pre=cur;
//                    cur=cur.next;
//                }else{
//                    break;
//                }
//            }
//            // 插入到当前节点的前一个节点
//            pre.next=node;
//            node.next=cur;
//
//            node=next;
//        }
//        return dummy.next;
//    }
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);

        ListNode pre = dummy;//指向要插入的前一个节点
        ListNode cur = head;
        while (cur != null) {
            while (pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }
            //先记录后一个节点
            ListNode next = cur.next;

            cur.next = pre.next;
            pre.next = cur;

            pre = dummy;//重置pre
            //更新cur
            cur = next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        L147 l147 = new L147();
        ListNode listNode = l147.insertionSortList(ListNode.build());
        System.out.println(listNode);
    }
}
